////////////////////////////////////////////////////////////////////////////
//
//  Crytek Engine Source File.
//  Copyright (C), Crytek Studios, 2002.
// -------------------------------------------------------------------------
//  File name:   ParticleUtils.h
//  Version:     v1.00
//  Created:     11/03/2010 by Corey (split out from other files).
//  Compilers:   Visual Studio.NET
//  Description: Splitting out some of the particle specific containers to here.
//							 Will be moved to a proper home eventually.
// -------------------------------------------------------------------------
//  History:
//
////////////////////////////////////////////////////////////////////////////

#ifndef __particleutils_h__
#define __particleutils_h__
#pragma once

#include "CryArray.h"

#if defined(__SPU__) || defined(_DEBUG)
	#define PARTICLE_SPU_CACHE
	// Special version for SPUs, prefetches and caches elements and transfers them back asynchronously
	// Current, previous, and next elements cached; previous in order to modify links during deletion
#endif

//////////////////////////////////////////////////////////////////////////
// Classes specifying initialization arguments.
struct InitDefault
{
	template<class T>
	void operator() (T* p) const
		{ new(p) T(); }
};

template<class A1>
struct Init1
{
	A1 a1;

	Init1(A1 const& a1_ = A1())
		: a1(a1_) {}

	template<class T>
	void operator() (T* p) const
		{ new(p) T(a1); }
};

template<class A1>
Init1<A1> InitArg(const A1& a1)
{
	return Init1<A1>(a1);
}


//////////////////////////////////////////////////////////////////////////
// A variable-sized list of items with a pre-allocated maximum.
// Allows efficient element deletion during iteration.

template<class T, class TAlloc, bool bReuse = false, class TInit = InitDefault>
class ParticleCollection
{
public:

	typedef int size_type;

	ParticleCollection( const TInit& init = TInit() )
		: m_Init(init)
	{ 
		reset(); 
	}

	~ParticleCollection()
	{
		clear();
	}

	size_type size() const
	{
		return m_Count;
	}

	const T& front() const
	{
		assert(!empty());
		return *get_elem(head_index());
	}

	void reserve(size_type nReserveCount)
	{
		const int nStartIndex = m_ElemList.size();
		nReserveCount += 2;
		if (nReserveCount <= nStartIndex)
			return;

		// Allocate new elems, and add to free list
		m_ElemList.resize(nReserveCount);
		for (int i = nStartIndex; i < nReserveCount; ++i)
		{
			ListElem& elem = m_ElemList[i];
			if (!m_Alloc.Allocate(elem.m_data))
			{
				// Allocation failed.
				m_ElemList.resize(i);
				break;
			}
			if (bReuse)
			{
				// Initialise on allocation.
				m_Init(elem.m_data);
			}
			add_to_freelist(i);
		}
		validate();
	}

	size_type capacity() const 
	{
		return m_ElemList.size()-2;
	}

	bool empty() const
	{
		return size() == 0;
	}

	void clear()
	{
		if (capacity() > 0)
		{
			if (!bReuse)
			{
				// Destruct active objects.
				for (int n = tail_index(); valid_index(n); n = prev_index(n))
				{
					get_elem(n)->~T();
				}
			}

			for (int i = m_ElemList.size()-1; valid_index(i); --i)
			{
				// We need to iterate through all the elements of m_ElemList here because,
				// regardless of the number of particles that were actually used, all the
				// memory that was allocated during the reserve call must be freed here.
				ListElem& elem = m_ElemList[i];
				if (bReuse)
				{
					// Destruct on deallocation.
					elem.m_data->~T();
				}
				m_Alloc.Deallocate(elem.m_data);
			}
		}
		reset();
	}

	T* push_back()
	{
		return insert(end_index());
	}

	T* push_front()
	{
		return insert(head_index());
	}

	void GetMemoryUsage(ICrySizer* pSizer) const
	{
		pSizer->AddObject(this, m_ElemList.get_alloc_size() + (capacity()*sizeof(T)));
	}

private:

	struct ListElem
	{
		T* m_data;
		int	next;
		int	prev;
	};

public:

	//////////////////////////////////////////////////////////////////////////
	// Traversal classes.
	// Base class templated for direction, and const or non-const access














	template<bool bReverse, class CL, class CT>
	class base_traverser
	{
public:

		// Version for SPUs, prefetches the elements and transfers em back asynchronously.
		ILINE base_traverser(CL& array)
		: m_pList(&array)
		{
			m_nIndex = bReverse ? array.tail_index() : array.head_index();




		}















		ILINE operator bool() const
		{
			return m_pList->valid_index(m_nIndex);
		}

		ILINE CT* operator->()
		{
			return cur_elem();
		}

		ILINE CT& operator*()
		{
			return *cur_elem();
		}

		ILINE void operator++()
		{
			// go to next element
			m_nIndex = m_pList->next_index( m_nIndex, bReverse );




















		}

		void erase()
		{
			if (!bReuse)
			{
				// call destructor
				cur_elem()->~T();
			}
			m_nIndex = m_pList->erase_link( m_nIndex, bReverse );
























		}

		T* insert()
		{
			return non_const(*m_pList).insert(m_nIndex);
		}

	private:

		ILINE bool valid_index(int index) const
		{
			return m_pList->valid_index(index);
		}

		ILINE CT* cur_elem()
		{





			return m_pList->get_elem(m_nIndex);

		}


































































































		CL*						m_pList;
		int						m_nIndex;
	};

	//////////////////////////////////////////////////////////////////////////
	typedef base_traverser<false, ParticleCollection, T>
		traverser;

	typedef base_traverser<false, const ParticleCollection, const T>
		const_traverser;

	typedef base_traverser<true, ParticleCollection, T>
		reverse_traverser;

	typedef base_traverser<true, const ParticleCollection, const T>
		reverse_const_traverser;

private:

	const T* get_elem(int index) const
	{
		return m_ElemList[index].m_data;
	}

	T* get_elem(int index)
	{
		return m_ElemList[index].m_data;
	}

	int head_index() const
	{
		return m_ElemList.front().next;
	}

	int tail_index() const
	{
		return m_ElemList.front().prev;
	}

	static int end_index()
	{
		return 0;
	}

	ListElem& end_list()
	{
		return m_ElemList[0];
	}

	static int free_index()
	{
		return 1;
	}

	ListElem& free_list()
	{
		return m_ElemList[1];
	}

	bool valid_index(int index) const
	{
		assert(index >= 0 && index < m_ElemList.size());
		return index > 1;
	}

	ILINE int next_index(int index) const
	{		
		return m_ElemList[index].next;
	}

	ILINE int prev_index(int index) const
	{		
		return m_ElemList[index].prev;
	}

	ILINE int next_index(int index, bool bReverse) const
	{
		assert(&m_ElemList[index].prev == &m_ElemList[index].next + 1);
		return (&m_ElemList[index].next) [bReverse];
	}

	void reset()
	{
		m_ElemList.resize(2);
		m_ElemList.shrink();
		end_list().next = end_list().prev = end_index();
		end_list().m_data = NULL;
		free_list().next = free_list().prev = free_index();
		free_list().m_data = NULL;

		m_Count = 0;
		validate();
	}

	SPU_NO_INLINE int alloc_new_index()
	{
		assert(m_Count < capacity());

		m_Count++;

		// Get element from front of freelist queue.
		int index = free_list().next;
		assert(valid_index(index));
		ListElem& free_elem = m_ElemList[index];

		m_ElemList[free_elem.prev].next = free_elem.next;
		m_ElemList[free_elem.next].prev = free_elem.prev;

		return index;
	}

	SPU_NO_INLINE T* insert(int next_index)
	{
		if (size() >= capacity())
			return 0;

		int index = alloc_new_index();
		assert(valid_index(index));
		ListElem& rCurElem = m_ElemList[index];

		// Update links.
		ListElem& rNextElem = m_ElemList[next_index];

		rCurElem.next = next_index;
		rCurElem.prev = rNextElem.prev;

		m_ElemList[rCurElem.prev].next = index;
		m_ElemList[rCurElem.next].prev = index;

		validate();

		T* obj = get_elem(index);

		if (!bReuse)
		{
			// initialise object
			new(obj) T();
		}
		return obj;
	}

	SPU_NO_INLINE void add_to_freelist(const int index)
	{
		// Add to end of freelist queue.
		assert(valid_index(index));
		ListElem& rCurElem = m_ElemList[index];
		rCurElem.next = free_index();
		rCurElem.prev = free_list().prev;
		m_ElemList[free_list().prev].next = index;
		free_list().prev = index;
	}

	SPU_NO_INLINE int erase_link(int index, bool bReverse)
	{
		assert(m_Count > 0);

		ListElem& elem = m_ElemList[index];		
		int ret = bReverse ? elem.prev : elem.next;

		// Update links.
		m_ElemList[elem.prev].next = elem.next;
		m_ElemList[elem.next].prev = elem.prev;

		add_to_freelist(index);

		m_Count--;

		validate();
		return ret;
	}

	void validate()
	{
#ifdef _DEBUG
		assert(m_Count >= 0 && m_Count <= capacity());
		assert(m_ElemList[0].m_data == NULL);
		assert(head_index() < m_ElemList.size());
		assert(tail_index() < m_ElemList.size());
		assert(prev_index(head_index()) == end_index());
		assert(next_index(tail_index()) == end_index());
		assert(free_list().next < m_ElemList.size());
		assert(free_list().prev < m_ElemList.size());

		for (int i = 2; i < m_ElemList.size(); i++)
		{
			assert(m_ElemList[i].m_data && m_ElemList[i].m_data != (CParticle*)0xDEDEDEDE);
		}

		int prev = end_index();
		int nUsed = 0;
		for (int index = head_index(); valid_index(index); index = next_index(index), nUsed++)
		{
			assert(prev_index(index) == prev);
			prev = index;
		}
		assert(nUsed == size());

		prev = free_index();
		int nFree = 0;
		for (int index = free_list().next; valid_index(index); index = next_index(index), nFree++)
		{
			assert(prev_index(index) == prev);
			prev = index;
		}
		assert(nFree == capacity() - size());
#endif // _DEBUG
	}

	FastDynArray<ListElem>	m_ElemList;		// Bi-directional list to manager the order of elements.
																		 		// Has capacity+2 entries: first entry contains head/tail indices of main list, second entry of free list.
	size_type								m_Count;			// Count of currently active elements.
	TAlloc									m_Alloc;			// Instance of allocator (typically no data)
	TInit										m_Init;				// Common element initialization data
};

//////////////////////////////////////////////////////////////////////////
// class to collect information if a ParticleContainer is updatable on SPU
class SpuUsage
{
public:
	SpuUsage( const string &sName, int nNumParticle ) : m_sName(sName), m_nNumParticle(nNumParticle) {}
	void SetCause( const string &sCause ) { m_sCause = sCause; }

	const char* Name() const { return m_sName.c_str(); }
	const char* Cause() const { return m_sCause.c_str(); }
	int NumParticle() const { return m_nNumParticle; }

	bool operator < ( const SpuUsage &other ) const { return m_nNumParticle > other.m_nNumParticle; }
private:
	string m_sName;
	string m_sCause;
	int m_nNumParticle;
};

typedef std::vector<SpuUsage> VecSpuUsageT;


extern ITimer* g_pParticleTimer;

// This mirrors the functionality in Cry3DEngineBase.h but using the particle timer



















typedef ITimer ParticleTimer;
ILINE ParticleTimer* GetParticleTimer()
{
	return g_pParticleTimer;
}



#endif // __particleutils_h__
